package com.yoshino.leetcode.interview150.backend;

import java.util.*;
import java.util.stream.Collectors;

class Solution {

    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return res;
        }
        String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        backTracking(digits, numString, 0);
        return res;
    }

    private void backTracking(String digits, String[] numString, int ind) {
        if (digits.length() == ind) {
            res.add(sb.toString());
            return;
        }
        String str = numString[digits.charAt(ind) - '0'];
        for (int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));
            backTracking(digits, numString, ind + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    List<List<Integer>> res2 = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backCombine(n, 0, k, new Integer[k], 0);
        return res2;
    }

    private void backCombine(int n, int ind, int k, Integer[] cur, int index) {
        if (k == index) {
            res2.add(Arrays.stream(cur).collect(Collectors.toList()));
            return;
        }
        for (int i = ind + 1; i <= n; i++) {
            cur[index] = i;
            backCombine(n, i, k, cur, index + 1);
        }
    }

    List<List<Integer>> res3 = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        List<Integer> cur = new ArrayList<>();
        if (n == 1) {
            cur.add(nums[0]);
            res3.add(cur);
            return res3;
        }
        boolean[] visited = new boolean[n];
        back(n, 0, cur, visited, nums);
        return res3;
    }

    private void back(int n, int ind, List<Integer> cur, boolean[] visited, int[] nums) {
        if (ind == n) {
            res3.add(new ArrayList<>(cur));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                cur.add(nums[i]);
                back(n, ind + 1, cur, visited, nums);
                cur.remove(cur.size() - 1);
                visited[i] = false;
            }
        }
    }

    List<List<Integer>> res4 = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        if (candidates[0] > target) {
            return res4;
        }
        back4(candidates, 0, target, new ArrayList<>());
        return res4;
    }

    private void back4(int[] candidates, int ind, int target, List<Integer> cur) {
        if (target == 0) {
            res4.add(new ArrayList<>(cur));
            return;
        } else if (target < 0) {
            return;
        } else {
            for (int i = ind; i < candidates.length; i++) {
                if (target - candidates[i] < 0) {
                    return;
                }
                cur.add(candidates[i]);
                back4(candidates, i, target - candidates[i], cur);
                cur.remove(cur.size() - 1);
            }
        }
    }

    public int totalNQueens(int n) {
        if (n == 1) {
            return 1;
        }
        if (n < 4) {
            return 0;
        }
        Set<Integer> cx = new HashSet<>();
        Set<Integer> rx = new HashSet<>();
        int[] temp = new int[n + 1];
        Arrays.fill(temp, -1);
        // 用于保存结果
        temp[n] = 0;
        backTracking(n, temp, cx, rx, 0);
        return temp[n];
    }

    private void backTracking(int n, int[] temp, Set<Integer> cx, Set<Integer> rx, int ind) {
        if (n == ind) {
            temp[n]++;
        } else {
            // i：行，j：列
            for (int i = 0; i < n; i++) {
                if (temp[i] != -1) {
                    // 已经有棋子
                    continue;
                }
                // 斜线，左下向右上的
                int add = i + ind;
                if (cx.contains(add)) {
                    // 在一条斜线上
                    continue;
                }
                // 斜线：左上到右下
                int sub = i - ind;
                if (rx.contains(sub)) {
                    continue;
                }
                temp[i] = ind;
                cx.add(add);
                rx.add(sub);
                backTracking(n, temp, cx, rx, ind + 1);
                temp[i] = -1;
                cx.remove(add);
                rx.remove(sub);
            }
        }
    }

    List<String> gres = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        back(new StringBuilder(), n, 0, 0);
        return gres;
    }

    private void back(StringBuilder sb, int n, int l, int r) {
        if (l > n || r > n || l < r) {
            return;
        }
        if (l == n && r == n) {
            gres.add(sb.toString());
            return;
        }
        back(sb.append('('), n, l + 1, r);
        sb.deleteCharAt(sb.length() - 1);
        back(sb.append(')'), n, l, r + 1);
        sb.deleteCharAt(sb.length() - 1);
    }

    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        char start = word.charAt(0);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (start == board[i][j]) {
                    if (back(board, word, 0, visited, i, j)) {
                        return true;
                    }
                }
            }

        }
        return false;
    }

    private boolean back(char[][] board, String word, int ind, boolean[][] visited, int i, int j) {
        if (ind == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j]) {
            return false;
        }
        if (board[i][j] == word.charAt(ind)) {
            visited[i][j] = true;
            boolean res = back(board, word, ind + 1, visited, i + 1, j) ||
                    back(board, word, ind + 1, visited, i, j + 1) ||
                    back(board, word, ind + 1, visited, i - 1, j) ||
                    back(board, word, ind + 1, visited, i, j - 1);
            if (res) {
                return true;
            }
            visited[i][j] = false;
        }
        return false;
    }

    public static void main(String[] args) {
        new Solution().totalNQueens(4);
    }
}